package com.SchoolGuide;

import java.util.Scanner;

public class AMGraph<T> {
    protected static final int MAX_WEIGHT = 0x0000ffff;    //最大值∞
    protected static final int maxVexNum = 20;        //最大顶点数
    T[] vexs; //顶点数组
    int[][] arcs;    //邻接矩阵
    int vexNum;        //顶点数
    int arcNum;        //边数
    boolean[] visited; //图的成员变量

    public AMGraph() {  //构造不含顶点和边的图
        vexs = (T[]) new Object[maxVexNum];  //根据最大顶点数构造顶点数组
        arcs = new int[maxVexNum][maxVexNum];  //根据最大顶点数构造边数组
        this.vexNum = 0;  //实际顶点数为0
        this.arcNum = 0;  //实际边数为0
    }

    public int locateVex(T v) {
        for (int i = 0; i < this.vexNum; i++) {
            if (v.equals(this.vexs[i])) return i;
        }
        return -1;
    }

    public void createUDN() { //根据顶点数组和边数组，建立无向网
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入顶点数和边数:");
        this.vexNum = sc.nextInt();  //实际顶点数
        this.arcNum = sc.nextInt();  //实际边数
        System.out.println("请输入" + this.vexNum + "个顶点,以空格隔开");
        sc.nextLine();
        String s = sc.nextLine();
//        String s = sc.next();
        String[] str = s.split(" ");
        for (int i = 0; i < this.vexNum; i++) {  //复制顶点至顶点数组
            this.vexs[i] = (T) str[i];
        }
        for (int i = 0; i < maxVexNum; i++) {  //初始化邻接矩阵为0 初始化二维数组
            for (int j = 0; j < maxVexNum; j++)
                arcs[i][j] = MAX_WEIGHT;
        }
        System.out.println("请输入" + this.arcNum + "条边:（v1,v2,w:权值）");
        for (int k = 0; k < this.arcNum; k++) { //输入k条边
            s = sc.next();//输入一条边
            str = s.split(",");  // 以“,”为分隔划分顶点
            T v1 = (T) str[0];
            T v2 = (T) str[1];
            int w = Integer.parseInt(str[2]);//获取到权值
            int i = locateVex(v1);  //确定顶点v1的下标
            int j = locateVex(v2);  //确定顶点v2的下标
            if (i == -1 || j == -1) throw new IndexOutOfBoundsException("非法边");
            arcs[i][j] = w;
            arcs[j][i] = arcs[i][j];
        }
    }

    public void DFS(int v) { //v为起始顶点(编号）进行一次深度优先搜索
        System.out.print(this.vexs[v] + " "); //访问顶点v
        visited[v] = true; //访问后立即修改辅助数组标志
        int j;
        for (j = 0; j < this.vexNum; j++)
            if (this.arcs[v][j] < MAX_WEIGHT && visited[j] == false)
                DFS(j);
    }

    public void DFSTraverse() { //深度优先遍历
        visited = new boolean[vexNum];
        //visited是图的成员变量
        for (int v = 0; v < this.vexNum; v++)
            visited[v] = false;
        for (int v = 0; v < this.vexNum; v++)
            if (visited[v] == false) DFS(v);
    }

    public void BFS(int v) {
        LinkQueue<Integer> q = new LinkQueue<Integer>();
        System.out.print(this.vexs[v]);
        visited[v] = true;
        q.enQueue(v);  //v入队
        while (!q.isEmpty()) {
            int u = q.delQueue(); //删除队首元素
            for (int j = 0; j < this.vexNum; j++) {
                if (this.arcs[u][j] < MAX_WEIGHT && !visited[j]) {
                    System.out.print(this.vexs[j] + " ");
                    visited[j] = true;
                    q.enQueue(j);
                } //end if
            } //end for
        } //end while
    }

    public void BFSTraverse() {
        visited = new boolean[vexNum]; //visited是图的成员变量
        for (int v = 0; v < this.vexNum; v++) visited[v] = false;
        for (int v = 0; v < this.vexNum; v++) {
            if (visited[v] == false)
                BFS(v);
        }
    }


}



